1. Field of the Invention
The present invention relates to a multiplier, and particularly to a high-speed multi-path serial-parallel multiplier.
2. Description of the Prior Art
Multipliers are classified into parallel multipliers and serial-parallel multipliers. The parallel multipliers are employed for signal processing VLSIs. The parallel multipliers add all partial products to one another at once, thereby realizing a very high processing speed. They, however, require a large amount of hardware so that they are not suitable for general-purpose signal processors.
On the other hand, the serial-parallel multipliers require a small amount of hardware so that they are suitable for general use. The serial-parallel multipliers, however, must repeat the addition arithmetic several times in conducting multiplication, thereby consuming a long processing time.
FIG. 1 shows an example of such serial-parallel multiplier. A register 101 holds a multiplier Y. A controller 103 scans the multiplier Y from its lower bits and controls a selector 105 in response to each of the scanned bits that may be 0 or 1. The selector 105 provides an adder 109 with a partial product, i.e., a multiplicand X stored in a register 107 or string of 0s. The adder 109 adds the partial product to an intermediate result calculated so far. A shifter 111 shifts the addition result one bit to the right. A register 113 holds the shifted result as an intermediate result, which is transferred again to the adder 109. After a partial product for a most significant bit of the multiplier Y is added, the adder 109 provides a final result of multiplication. This technique requires 32 cycles for calculating a multiplication of 32 bits.
One effective technique for reducing the number of additions to be done in the serial-parallel multiplier is to employ a Booth algorithm. This technique manipulates a plurality of bits of a multiplier to reduce the number of partial products to be processed.
FIG. 2 shows a multiplier employing a quadratic Booth algorithm. The quadratic Booth algorithm conducts multiplication according to the following equations: ##EQU1##
It is supposed y.sub.-1 =0. As is apparent from the equation (1), each three bits of a multiplier Y are collectively evaluated to halve the number of partial products. According to a value calculated between the parentheses of the equation (1), a decoder 115 provides a processing circuit 123 with a shifting signal 117 (multiplying by 2), an inverting signal 119 (multiplying by -1), or a switching signal 121 (generating a string of 0s). A shifter 125 shifts an output of an adder 109 by two bits. This technique may halve the number of additions but must still repeat an addition process 16 times in multiplying a number of 32 bits.
In this way, the conventional serial-parallel multipliers involve many addition processes and require a long processing time.